package com.programmercarl.dp;

/**
 * https://leetcode.cn/problems/target-sum/description/
 * 494.目标和 参考
 *
 * @author 田雨龙
 * @create 2025-02-17 21:26
 */
public class Test10 {
    public static void main(String[] args) {
        Math.pow(2.0, 1);
    }


    /**
     * 回溯方法 超时
     *
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target) {
        int[] ans = new int[1];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        backTracking(nums, (sum + target) / 2, 0, 0, ans);
        return ans[0];
    }

    public void backTracking(int[] nums, int target, int tempSum, int index, int[] ans) {
        if (target == tempSum) {
            ans[0]++;
            return;
        }
        for (int i = index; i < nums.length && tempSum + nums[i] <= target; i++) {
            tempSum += nums[i];
            backTracking(nums, target, tempSum, i + 1, ans);
            tempSum -= nums[i];
        }
    }

}
